import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/24 15:29
 * @description 思路：根据快照id存储不同时期的快照，可以用hashmap O(1)复杂度获取
 */
public class SnapshotArray {
    List<TreeMap<Integer, Integer>> arr = new ArrayList<>();
    int snap = 0;

    public SnapshotArray(int length) {
        for (int i = 0; i < length; i++) {
            arr.add(new TreeMap<>());
        }
    }

    public void set(int index, int val) {
        // 修改的是索引index处的值，那么将每次快照的值用treeMap的值排序起来
        TreeMap<Integer, Integer> tm = arr.get(index);
        tm.put(snap, val);
    }

    public int snap() {
        return snap++;
    }

    public int get(int index, int snap_id) {
        TreeMap<Integer, Integer> tm = arr.get(index);
        // 获取最近一次的修改 <= snap_id, 当然，此处可以使用二分查找，找到第一次大于等于snap_id的下标，大于减少，等于不变
        Integer key = tm.floorKey(snap_id);
        return key == null ? 0 : tm.get(key);
    }

}
